The article by SONG GUO ET AL: “A Permutation-Based Multi-Polynomial Scheme for Pairwise Key Establishment in Sensor Networks”, COMMUNICATIONS (ICC), 2010 IEEE INTERNATIONAL CONFERENCE ON, IEEE, PISCATAWAY, N.J., USA, 23 May 2010 (2010-05-23), pages 1-5, discloses a prior art solution.
Given a communications network comprising multiple network devices, it is a problem to set up secure connections between pairs of such network devices. One way to achieve this is described in C. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro and M. Yung, “Perfectly-Secure Key distribution for Dynamic Conferences”, Springer Lecture Notes in Mathematics, Vol. 740, pp. 471-486, 1993 (referred to as ‘Blundo’).
It assumes a central authority, also referred to as the network authority or as the Trusted Third Party (TTP), that generates a symmetric bivariate polynomial f(x,y), with coefficients in the finite field F with p elements, wherein p is a prime number or a power of a prime number. Each device has an identity number in F and is provided with local key material by the TTP. For a device with identifier η, the local key material are the coefficients of the polynomial f(η,y).
If a device 11 wishes to communicate with device η′, it uses its key material to generate the key K(η, η′)=f(η, η′). As f is symmetric, the same key is generated.
A problem of this key sharing scheme occurs if an attacker knows the key material of t+1 or more devices, wherein t is the degree of the bivariate polynomial. The attacker can then reconstruct the polynomial f(x,y). At that moment the security of the system is completely broken. Given the identity numbers of any two devices, the attacker can reconstruct the key shared between this pair of devices.